The present invention relates generally to the field of electronic computer systems, and more particularly, is directed to a method and apparatus for scheduling the execution of a plurality of processing tasks within a computer system.
A conventional computer system, such as shown in FIG. 1, comprises a number of interrelated elements including RAM memory 1 and ROM memory 2 where instructions and temporary data storage areas of a computer program reside, mass storage and Input/Output (I/O) peripherals 3 which allow the computer to access mass storage devices, such as magnetic disk and tape units, and to communicate with the outside world through such devices as printers, user interactive terminal display 4 which allows the computer to communicate with the user and a central processing unit (CPU) 5 which supervises the flow of information between the various elements of the system and which performs logic calculations and other functions based on instructions in the computer program and data associated with the program.
Present day large-scale computer systems are quite sophisticated in operation and are often very expensive to manufacture and operate. In order to provide more access to such systems at a reasonable cost, the concept of "time sharing" was developed. In a time sharing computer system, a number of programs reside in the computer at the same time and seemingly run simultaneously. Each program is referred to as a task or job and though it may appear to the casual user that the computer is continuously devoting its full attention to the task being performed for the user, in actuality, each task receives only a fraction of the computer's time before the computer moves on to other tasks in "round-robin" fashion. Typically, each computer user is connected to a separate task. In addition, there may be other tasks which perform internal functions for the computer system or which yield results which will eventually go to a person who is not currently using the computer.
In conventional computer systems, a facility known as an "interrupt" allows the execution of the CPU to be interrupted periodically based on requests for service from internal or external devices or based on the passage of a certain amount of time. When an interrupt occurs, the CPU stores information about the task it was performing when the interrupt occurred and then executes another task determined by the nature of the interrupt. The stored information allows the CPU to resume execution of the task which was interrupted once it has finished performing the task required by the interrupt. The CPU may also execute other tasks required by other interrupts before returning to the original task.
A time sharing computer system, whether it be driven by interrupts or by some other scheme, must have means for selecting the task which will be executed by the CPU and deciding how long the CPU will execute the task before reassigning the CPU to another task. Such means can be referred to as a task scheduler. The operation of the task scheduler is itself supervised by the CPU. The CPU time spent in supervising the operation of the task scheduler is overhead and should be minimized.
Tasks within a time sharing computer system can be divided into the following three categories based on the criticality of the timeliness of the computer response to external events related to the task.
(1) "Real-time" tasks where the essence of the computer function is to provide a rapid response to external events. An example of this type of task is the guidance control program for a missile. If the computer is unable to provide rapid responses to course deviations or changing fuel weight, the missile will go off course. PA1 (2) "Interactive" tasks where a delay in response is inconvenient and inefficient but is not disastrous. An example of this type of task is a program which provides information about a customer's account status to a bank teller. If the computer is unable to provide a rapid response, the teller's time will be wasted and a waiting customer will be annoyed, but the bank will not become insolvent. PA1 (3) "Background" tasks where response time to external events is not important. An example of this type of task is a program to print bank account summary statements at the end of the month.
Interactive tasks may be subdivided into two additional categories. It is generally accepted that it is desirable to give precedence to short interactive inquiries over requests for service which will take an extended period of time. For example, two bank managers may both issue "interactive" requests to the bank's computer. One request is to display the current balance for an account, the other is to sort all accounts alphabetically and produce a complex report. Usually, it is desirable to give precedence to the short interactive request rather than to delay it while computing the complex report.
Various task schedulers have been proposed and implemented which are somewhat adequate for servicing real-time or background type tasks. One approach in wide use is to assign fixed priorities to each task and base the scheduling of tasks solely on these priorities. While this approach may be suited for dedicated real-time applications, it is unacceptable for interactive applications where the nature of the interactive request is more important than a previously specified priority. Another approach is to use a fixed "time-slice" to direct the CPU to one task after another in a round-robin fashion. This approach has the effect of giving all tasks equal priority. Neither of these scheduling methods is adequate for a computer system which supports real-time, interactive, and background tasks.
The ideal task scheduler should recognize the nature of each task and allocate the CPU in such a fashion as to provide optimum responsiveness to the tasks based on how important rapid response is to each task. This level of sophistication in task schedulers known in the prior art has not been achieved heretofore. The problem in achieving such a level of sophistication is compounded by the fact that the classification of each task (i.e., real-time, interactive, or background) cannot be determined by the task scheduler without information being provided by the computer operator and because the nature of each task may change dynamically over time. Applicant has discovered a novel solution to this problem and accordingly has developed a task scheduler which is far superior to those known in the art.